#include <iostream>
#include <vector>
#define INF 1000000000
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1, vector<int>(n + 1, INF));
    int a, b, w;
    int i, j, k;
    for (i = 1; i <= n; i++)
        g[i][i] = 0;
    for (i = 0; i < m; i++)
    {
        cin >> a >> b >> w;
        if (w < 0)
            w = INF;
        w = min(w, g[a][b]);
        g[a][b] = w;
    }
    vector<vector<int>> A = g;
    // 下面这个三层循环是完成了以k为中间点对所有的顶点对(i, j)进行检测和修改
    for (k = 1; k <= n; ++k)
    {
        for (i = 1; i <= n; ++i)
        {
            for (j = 1; j <= n; ++j)
            {
                if (A[i][j] > A[i][k] + A[k][j])
                    A[i][j] = A[i][k] + A[k][j];
            }
        }
    }

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            cout << A[i][j] << ' ';
        cout << endl;
    }

    return 0;
}